package com.zjsru.oneDay202210;

/**
 * @Author: CookLee
 * @Date: 2022/10/20
 * 第K个语法符号
 *我们构建了一个包含 n 行( 索引从 1  开始 )的表。首先在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。
 * 例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。
 * 给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）
 *
 * 输入: n = 1, k = 1
 * 输出: 0
 * 解释: 第一行：0
 *
 * 输入: n = 2, k = 1
 * 输出: 0
 * 解释:
 * 第一行: 0
 * 第二行: 01
 *
 * 输入: n = 2, k = 2
 * 输出: 1
 * 解释:
 * 第一行: 0
 * 第二行: 01
 */
public class KthGrammar {
    public int kthGrammar(int n, int k) {
        return dfs(n,k,1) == 0 ? 1 :0;
    }
    /**
     * 倒推验证:假设第 n 行第 k 为 1，若能倒推出首行为 0，说明假设成立，返回 1，否则返回 0。
     * */
    private int dfs(int n, int k, int cnr) {
        if (n == 1) {
            return cnr;
        }
        //当前列 k 为偶数且 cur=0」或「当前列 k 为奇数且 cur=1」,说明当前列所在的组为 10，由此可推出其是由上一行的 1 拓展而来
        if ((k % 2 == 0 && cnr == 0) || (k % 2 == 1 && cnr == 1)) {
            return dfs(n - 1, (k - 1) / 2 + 1, 1);
        } else {
            //说明当前列所在的组为 01，由此可推出其是由上一行的 0 拓展而来
            return dfs(n - 1, (k - 1) / 2 + 1, 0);
        }
    }
    
    public static void main(String[] args) {
        KthGrammar kthGrammar = new KthGrammar();
        int n = 2, k = 2;
        System.out.println(kthGrammar.kthGrammar(n, k));
    }

}
